//od_中等.需要多少面试官/未测试
//公司正在组织集中面试，每场面试需要一个面试官，现在以数组的形式给出了每场面试的开始时间和结束时间的
//时间安排表 [si, ei] (si < ei)），为避免面试冲突，请问至少需要多少位面试官，才能满足这些面试安排。
//示例 1:
//输入: [[0, 30],[5, 10],[15, 20]]输出: 2
//示例 2:
//输入: [[7,10],[2,4]]输出: 1
//这是一道时间规划问题
//思路：先排序，然后比较endTime 和 startTime

//n为每个需要面试的总场次，m每个面试官最大面试场次，
//后面给出每场面试的开始和结束时间，面试官在一段时间内只能面试一个人
//输入：n  总场次如 5
//m 每人人最大面试场次如 2
//n组  如{
//[1,2],[2,5],[4, 30],[5, 10],[15, 20]
//}
//输出：最少面试官人数  如 3

//       2   3
//  1234567890123456789012345678901234567890
//  -
//   ---
//   ------------------------------------
//  -----
//    -----

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int needManger(vector<vector<int>>& meetings,int limit) {
  if (limit == 1) {
    return meetings.size();
  }
  typedef pair<int, int> pa;
  sort(meetings.begin(), meetings.end());
  //for (auto v : meetings) {printf("%d,%d\n", v[0], v[1]);}printf("\n");
  //先按照每一场会议的开始时间进行排序
  auto cmp = [](pair<int, int>& a, pair<int, int>& b) {return a.first > b.first; };
  priority_queue<pa, vector<pa>, decltype(cmp)> minHeap(cmp);
  int all = 1;
  minHeap.push({0,0});
  //小根堆
  for (auto meeting : meetings) {
    if (minHeap.empty() || minHeap.top().first > meeting[1]) {
      all++;
      minHeap.push({ meeting[1],1 });
    } else {
      auto mannger = minHeap.top();
      minHeap.pop();
      //如果已经达到上限了不用再放回到队列当中
      if (mannger.second < limit - 1) {
        mannger.second++;
        mannger.first = meeting[1];
        minHeap.push(mannger);
      }
    }
  }
  return all;
}

int main_viewer2() {
  vector<vector<int>> arr{ {3,17},{4,13},{5,6},{6,27} };
  cout << needManger(arr,3) << endl;
  return 0;
}
